import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
 * @author Eric Wu
 * @since 1.8
 */
public class Solution {


    private static final int MAX_INT = 0x0FFFFFFF;


    public static void main(String[] args) throws FileNotFoundException {


        System.setIn(new FileInputStream("input.txt"));

        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();

        for (int t = 1; t <= T; t++) {


            int cityNum = scanner.nextInt();

            int[] cost = new int[cityNum];
            for (int i = 0; i < cityNum; i++) {
                cost[i] = scanner.nextInt();
            }

            int[][] lines = new int[cityNum][cityNum];

            for (int i = 0; i < cityNum; i++) {
                for (int j = 0; j < cityNum; j++) {

                    lines[i][j] = scanner.nextInt();
                }
            }

            int result = solve(cityNum, cost, lines);


            System.out.println("# " + t + " " + result);

        }

    }


    private static int solve(int cityNum, int[] cost, int[][] lines) {

        boolean[] selectCity = new boolean[cityNum];
        for(int i=0;i<cityNum;i++){
            selectCity[i] = false;
        }
        selectCity[0] = true;
        int[] min = new int[]{MAX_INT};
        calculate(cityNum,cost,lines,0,min,selectCity);
        int temp = min[0];

        for(int i=0;i<cityNum;i++){
            selectCity[i] = false;
        }
        calculate(cityNum,cost,lines,0,min,selectCity);

        if(temp == MAX_INT){
            temp = 0;
            for(int i=0;i<cityNum;i++){
                temp+=cost[i];
            }
        }

        return temp>min[0]?min[0]:temp;

    }


    private static void calculate(int cityNum, int[] cost, int[][] lines, int depth, int[] min, boolean[] selectCity) {

        if (depth >= cityNum) {
            return;
        }

        for(int c=0;c<2;c++){

            if(c == 0){


                boolean[] flag = new boolean[cityNum];
                for(int i=0;i<cityNum;i++){
                    flag[i] = false;
                }
                flag[depth] = true;
                selectCity[depth] = true;
                for(int i=0;i<=depth;i++){
                    for(int j=0;j<cityNum;j++){

                        if(lines[i][j] == 1 && selectCity[i]){
                            flag[j] = true;
                        }

                    }
                }


                boolean connectedAll = true;
                for(int i=0;i<cityNum;i++){

                    if(!flag[i]){
                        connectedAll = false;
                        break;
                    }
                }

                if(connectedAll){
                    int sum = 0;
                    for(int i=0;i<cityNum;i++){
                        if(selectCity[i]){
                            sum+=cost[i];
                        }
                    }

                    if(sum<min[0]){
                        min[0] = sum;
                    }else{
                        continue;
                    }
                }else{
                    int sum = 0;
                    for(int i=0;i<cityNum;i++){
                        if(selectCity[i]){
                            sum+=sum;
                        }
                    }

                    if(sum>=min[0]){
                        continue;
                    }

                    calculate(cityNum,cost,lines,depth+1,min,selectCity);

                }


            }else{
                selectCity[depth] = false;
                calculate(cityNum,cost,lines,depth+1,min,selectCity);

            }



        }


    }


}
